<!DOCTYPE html>
<html lang="en">
<head>
  <meta charset="UTF-8">
  <meta http-equiv="X-UA-Compatible" content="IE=edge">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <title>Document</title>
</head>
<body>
  <script>
    // 题目: https://leetcode-cn.com/problems/valid-parentheses/

    // TODO: 分析
    // 新建一个栈(越靠后的左括号, 对应的右括号越靠前, 左括号想象成入栈操作, 右括号想象成出栈操作)
    // 遍历字符串, 遇到左括号入栈, 遇到和栈顶括号类型匹配的右括号就出栈, 类型不匹配直接判定为不合法
    // 最后栈空了就合法, 否则不合法



    // 时间复杂度: 一个 for 循环, 而且循环体内都是 O(1) 的复杂度, 即最后的时间复杂度为 O(n), n 为 s 的 length
    // 空间复杂度: 极端情况下, 会将 s 里面所有的字符都 push 到 stack 里, 因此空间复杂度是 O(n)
    const isValid = function (s) {
      // 判定字符串长度是否为奇数
      if (s.length % 2 === 1) return false;

      const stack = [];
      for (let i = 0; i < s.length; i ++) {
        const c = s[i];
        if (c === '(' || c === '{' || c === '[') {
          stack.push(c);
        } else {
          // 栈顶元素
          const t = stack[stack.length - 1];
          if (
            (t === '(' && c === ')') ||
            (t === '{' && c === '}') ||
            (t === '[' && c === ']')
          ) {
            stack.pop();
          } else {
            return false;
          }
        }
      }

      return stack.length === 0;
    }


    isValid('(())');
    isValid('((((((())}]');
  </script>
</body>
</html>